/*
 * @lc app=leetcode.cn id=10 lang=javascript
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
/**
 * @param {let} s
 * @param {let} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  // // 这题改为最优正则
  // switch (s) {
  //   case 'aaa':
  //     if (p === 'a*a' || p === 'ab*a*c*a') {
  //       return true
  //     }
  //   case 'bbbba':
  //     if (p === '.*a*a') {
  //       return true
  //     }
  //   case 'a':
  //     if (p === '.*..a*' || p === '.*..') {
  //       return false
  //     }

  //   default:
  //     break;
  // }
  // s = s.split('')
  // p = p.split('')
  // let p1, p2
  // while (p.length > 0) {
  //   p1 = p[0]
  //   p2 = p[1]
  //   console.log('-----------')
  //   console.log(p1)
  //   console.log(p2)
  //   if (p1 === '.' && p2 !== '*') {
  //     s.shift()
  //     p.shift()
  //     continue
  //   } else if (p1 === '.' && p2 === '*') {
  //     while(s.length > 0) {
  //       s.shift()
  //     }
  //   } else if (p1 !== '.' && p2 !== '*') {
  //     // console.log('-----' + p1)
  //     // console.log(s)
  //     if (p1 !== s.shift()) {
  //       return false
  //     }
  //     p?.shift()
  //     continue
  //   } else if (p1 !== '.' && p2 === '*') {
  //     while(s.length > 0) {
  //       if (p1 === s[0]) {
  //         s.shift()
  //       } else {
  //         break
  //       }
  //     }
  //   }
  //   p?.shift()
  //   p?.shift()
  // }
  // console.log(s)
  // console.log(p)
  // return s.length === 0

  let m = s.length // 字符串
  let n = p.length // 规则

  let f = Array(m + 1).fill([]).map(() => Array(n + 1).fill(false))
  f[0][0] = true
  for (let i = 0; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (p.charAt(j - 1) === '*') {
        f[i][j] = f[i][j - 2]
        if (matches(s, p, i, j - 1)) {
          f[i][j] = f[i][j] || f[i - 1][j]
        }
      } else {
        if (matches(s, p, i, j)) {
          f[i][j] = f[i - 1][j - 1]
        }
      }
    }
  }
  return f[m][n];
}

function matches (s, p, i, j) {
  if (i === 0) {
    return false
  }
  if (p.charAt(j - 1) === '.') {
    return true
  }
  return s.charAt(i - 1) === p.charAt(j - 1)
}
// console.log(isMatch("aab", "c*a*b"))
// console.log(isMatch("a", ".*..a*"))
// @lc code=end

